#pragma once
#include <assert.h>
#include <iostream>
using namespace std;
namespace apex
{
	template <class T>
	// 一、vector类
	class vector
	{
	public:
		// 迭代器
		typedef T *iterator;
		typedef const T *const_iterator;
		typedef __reverse_iterator<iterator, T &, T *> riterator;
		typedef __reverse_iterator<const_iterator, const T &, const T *> const_riterator;

	private:
		iterator _start;
		iterator _finish;
		iterator _end_of_storage;

	public:
		// 正向迭代器函数
		iterator begin()
		{
			return _start;
		}
		const_iterator begin() const
		{
			return _start;
		}
		iterator end()
		{
			return _finish;
		}
		const_iterator end() const
		{
			return _finish;
		}

		// 正向迭代器函数
		riterator rbegin()
		{
			return riterator(end());
		}
		const_riterator rbegin() const
		{
			return const_riterator(end());
		}
		riterator rend()
		{
			return riterator(begin());
		}
		const_riterator rend() const
		{
			return const_riterator(begin());
		}

		// 无参构造
		vector()
			: _start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
		{
		}

		// 有参构造
		// T()：匿名对象
		vector(size_t n, const T &val = T())
			: _start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
		{
			reserve(n);
			for (size_t i = 0; i < n; ++i)
			{
				push_back(val);
			}
		}

		// 迭代器构造
		// 为什么不直接用iterator？
		// iterator只能使用vector
		// 再定义一个模板：可以使用多种类型的迭代器
		template <class InputIterator>
		vector(InputIterator first, InputIterator last)
			: _start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
		{
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		// 拷贝构造传统写法1.0
		/*
		vector(const vector<T>& v)
		{
			size_t sz = v.size();
			_start = new T[sz];
			//0.size capacity都行：拷贝内容即可 有可能不对拷贝对象操作
			//1.拷贝的空间是size        对拷贝对象操作  -- 扩容
			//2.拷贝的空间是capacity  不对拷贝对象操作  -- 空间浪费

			//memcpy(_start, v._start, sizeof(T) * sz); ==》无法解决vector<vector<int>>
			//以及下方reserve的问题 使用赋值 -- 自定义类型调用它们各自的赋值重载 -- 实现二层深拷贝

			for (size_t i = 0; i < sz; ++i)
			{
				_start[i] = v._start[i];
			}

			_finish = _start + sz;
			_end_of_storage = _start + sz;
		}
		*/

		// 拷贝构造传统写法1.1
		/*
		vector(const vector<T>& v)
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			reserve(v.size());       //reserve开空间
			for (const auto& e : v)  //const：防止v被改变
			{
				push_back(e);
			}
		}
		*/

		// 拷贝构造高级写法
		void swap(vector<T> &v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_end_of_storage, v._end_of_storage);
		}
		vector(const vector<T> &v)
			: _start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
		{
			vector<T> tmp(v.begin(), v.end()); // 迭代器 -- push_back -- reserve -- 二层深拷贝
			swap(tmp);
		}

		// 赋值重载
		vector<T> &operator=(vector<T> v)
		{
			swap(v);
			return *this;
		}

		// 析构函数
		~vector()
		{
			delete[] _start;
			_start = _finish = _end_of_storage = nullptr;
		}

		// 获取capacity的大小(vector没有此变量)
		size_t capacity() const
		{
			return _end_of_storage - _start;
		}

		// 获取size的大小(vector没有此变量)
		size_t size() const
		{
			return _finish - _start;
		}

		// [] 重载
		T &operator[](size_t pos)
		{
			assert(pos < size());

			return _start[pos];
		}
		const T &operator[](size_t pos) const
		{
			assert(pos < size());

			return _start[pos];
		}

		// 扩容 -- 涉及到开新空间 -- 拷贝内容 -- 拷贝的可能是自定义类型
		void reserve(size_t n)
		{
			if (n > capacity())
			{
				size_t sz = size();
				T *tmp = new T[n];

				if (_start != nullptr)
				{
					// memcpy(tmp, _start, sizeof(T) * sz);

					for (size_t i = 0; i < sz; ++i)
					{
						tmp[i] = _start[i];
					}
					delete[] _start;
				}

				_start = tmp;
				_finish = _start + sz;
				_end_of_storage = _start + n;
			}
		}

		// 扩容 + 初始化
		void resize(size_t n, const T &val = T())
		{
			// 1. n > capacity         -- 扩容 + 初始化
			if (n > capacity())
			{
				reserve(n);
			}
			// 2. size < n < capacity  -- 初始化
			if (n > size())
			{
				while (_finish < _start + n)
				{
					*_finish = val;
					++_finish; // finish移到新的"end"==>_start + n
				}
			}
			// 3. n < size              -- 删除数据
			else
			{
				_finish = _start + n; // 直接更新finish即可
			}
		}

		// 增加数据                                        （可修改）
		// const：匿名对象  隐式转换（临时变量【具有常性】）  左值 + 右值
		void push_back(const T &x)
		{
			/*
				if (_finish == _end_of_storage)
				{
					reserve(capacity() == 0 ? 4 : capacity() * 2);
				}

				*_finish = x;
				++_finish;
			*/

			insert(end(), x);
		}

		// pop_back
		void pop_back()
		{
			assert(_finish > _start);
			--_finish;
		}

		// insert
		iterator insert(iterator pos, const T &x)
		{
			assert(pos >= _start && pos <= _finish);

			if (_finish == _end_of_storage)
			{
				size_t len = pos - _start;

				reserve(capacity() == 0 ? 4 : capacity() * 2); // 扩容后 空间地址更新 pos仍指向原空间pos处
				// 走下面的while时 访问pos --> error
				pos = _start + len; // 为防止pos失效 连带更新pos
			}

			// 挪动数据
			iterator end = _finish - 1;
			while (end >= pos)
			{
				*(end + 1) = *end;
				--end;
			}
			*pos = x;

			++_finish;

			return pos;
		}

		// erase
		iterator erase(iterator pos)
		{
			assert(pos >= _start);
			assert(pos < _finish);

			iterator begin = pos + 1;
			while (begin < _finish)
			{
				*(begin - 1) = *begin;
				++begin;
			}

			--_finish;

			if (size() < capacity() / 2)
			{
				// 缩容 -- 以时间换空间
				// 缩容--空间更新--pos失效--更新pos--只能解决形参作用域内的pos失效
				// 当再次erase--访问pos ：error
			}

			return pos; // 删除数据之后 返回pos --> pos指向被删除的值
						// 目标值被删除后 数据前移 pos指向空间不变 只不过pos指向的值是 目标值后的值
		}

		// front
		T &front()
		{
			assert(size() > 0);

			return *_start;
		}

		// back
		T &back()
		{
			assert(size() > 0);

			return *(_finish - 1);
		}
	};
	////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	// 二、命名空间内的函数

	// 增 删 [] size() 迭代器 范围for
	void test_vector1()
	{
		vector<int> v;

		// push_back
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(5);

		// []  size()
		for (size_t i = 0; i < v.size(); ++i)
		{
			cout << v[i] << " ";
		}
		cout << endl;

		// 正向迭代器
		vector<int>::iterator it = v.begin();
		while (it != v.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;

		// 反向迭代器
		vector<int>::riterator rit = v.rbegin();
		while (rit != v.rend())
		{
			cout << *rit << " ";
			++rit;
		}
		cout << endl;

		// pop_back
		v.pop_back();
		v.pop_back();

		// 范围for
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	// 迭代器失效问题(1) -- insert(野指针问题)
	void test_vector2()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(5);

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;

		auto p = find(v.begin(), v.end(), 3);
		if (p != v.end())
		{
			v.insert(p, 30);
			// 在p位置插入数据后不要访问p-->p可能失效：
			// 插入需要扩容 扩容会更新空间地址 pos仍指向源空间的pos处 pos失效
			// 即便改进了insert代码 更新了pos -->解决了insert中while循环内访问pos的问题
			// 但是形参改变不影响实参  在作用外pos仍失效
			// 为什么不使用引用？
			// v.insert(v.begin(), 1); -->
			// iterator begin()
			//{
			//	 return _start;
			// }
			// 返回临时拷贝--具有常性--与引用可以修改的特性不匹配
			// 那改成：const iterator& pos -->
			// 内部无法对_start修改
			//

			/*
			* cout << *p << endl;
			v.insert(p, 40);
			*/
		}

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	// erase
	void test_vector3()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;

		auto p = find(v.begin(), v.end(), 3);
		if (p != v.end())
		{
			v.erase(p);
		}

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;

		v.erase(v.begin());

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	// 迭代器失效问题(2) -- erase 删除所有的偶数 (迭代器位置问题)
	void test_vector4()
	{
		// 正常运行--lucky
		// 1 2 3 4 5 --> 1 3 5 -- it == end 循环结束
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(5);
		// 崩溃
		// 1 2 3 4 --> 1 4 -- end在4后一个 it在4后两个 it != end 循环无法结束
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		// 结果不对
		// 1 2 4 3 4 5 -- erase 2 --> 1 4 3 4 5  it再++ 直接跳过4
		v.push_back(1);
		v.push_back(2);
		v.push_back(4);
		v.push_back(3);
		v.push_back(4);
		v.push_back(5);

		auto it = v.begin();

		// 错误
		/*
		while (it != v.end())
		{
			if (*it % 2 == 0)
			{
				v.erase(it);
			}

			++it;
		}
		*/

		// 正确
		while (it != v.end())
		{
			if (*it % 2 == 0)
			{
				it = v.erase(it); // it不在++ 而是停留在此处
			}
			else // 是奇数才++
			{
				++it;
			}
		}

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	// 迭代器失效问题(3) -- insert (扩容野指针 + 迭代器位置问题)
	void test_vector5()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);

		// 在所有偶数前插入该数2倍的值
		auto it = v.begin();
		while (it != v.end())
		{
			if (*it % 2 == 0)
			{
				it = v.insert(it, *it * 2); // 1.it重新赋值：插入大概率回扩容 一旦扩容 空间更新 it成为野指针
				//  insert函数返回新的指向原位置的迭代器 it重新赋值 成功解决问题
				// 2.插入后不再 ++ ：使it停留在此处

				// 下面两次++是按题意 1 2 3 ——> 1 4 2 3
				// --> it指向4  ++两次指向3(即进行下一次寻找)
				++it;
				++it;
			}
			else
			{
				++it;
			}
		}

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	// 迭代器失效问题(4) -- erase (缩容野指针 + 迭代器位置问题)
	/*
	待实现
	*/

	// 总结：迭代器失效问题
	// 1.扩容导致的野指针问题
	// 2.插入或删除导致的迭代器位置错误问题

	// 拷贝构造
	void test_vector6()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(5);
		// 1 2 3 4 5
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
		// 拷贝构造
		vector<int> v1(v);
		v[0] *= 10; // 深拷贝
		// 10 2 3 4 5
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
		// 1 2 3 4 5
		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	// 迭代器构造
	void test_vector7()
	{
		string s("hello world");
		vector<int> vs(s.begin(), s.end());
		for (auto e : vs)
		{
			cout << e << " ";
		}
		cout << endl;

		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(5);

		vs = v;				  // 赋值重载：针对两个已经存在的对象
		vector<int> copy = v; // 拷贝构造 ==》copy(v);
		// copy不存在 用一个已有的对象去初始化一个新对象

		vs[0] *= 10;
		for (auto e : vs)
		{
			cout << e << " ";
		}
		cout << endl;

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	// 有参构造
	void test_vector8()
	{
		// C++引入了模板 ==》内置类型也可以有构造
		/*
		int i = 0;
		int j = int();
		int k = int(10);
		*/

		// 正常运行
		vector<int> v1(10);
		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;

		// 正常运行
		vector<char> v3(10, 'a');
		for (auto e : v3)
		{
			cout << e << " ";
		}
		cout << endl;

		// 编译错误：参数匹配
		//<int> v2(10, 1);
		// 1.vector(size_t n, const T & val = T()) ;
		// 2.vector(InputIterator first, InputIterator last);
		// 1.int-->u_int int-->T    匹配程度低
		// 2.int-->T     int-->T 【有解引用操作】

		// 修正1.0：
		vector<int> v2(10u, 1); // 第一种匹配程度变高 -- ok
		// 修正2.0：
		// vector(int n, const T & val = T()) ;
		for (auto e : v2)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	// resize
	void test_vector9()
	{
		vector<int> v1;
		v1.resize(10, 0);
		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;

		vector<int> v2;
		v2.reserve(10);
		v2.push_back(1);
		v2.push_back(2);
		v2.push_back(3);
		v2.push_back(4);
		v2.push_back(5);

		v2.resize(8, 8);
		for (auto e : v2)
		{
			cout << e << " ";
		}
		cout << endl;

		v2.resize(20, 20);
		for (auto e : v2)
		{
			cout << e << " ";
		}
		cout << endl;

		v2.resize(3);
		for (auto e : v2)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	// vv的深拷贝天坑
	void test_vector10()
	{
		class Solution
		{
		public:
			vector<vector<int>> generate(int n)
			{
				vector<vector<int>> Vv;
				Vv.resize(n);
				for (size_t i = 0; i < Vv.size(); ++i)
				{
					Vv[i].resize(i + 1, 0);
					Vv[i].front() = Vv[i].back() = 1;
				}

				for (size_t i = 0; i < Vv.size(); ++i)
				{
					for (size_t j = 0; j < Vv[i].size(); ++j)
					{
						if (Vv[i][j] == 0)
						{
							Vv[i][j] = Vv[i - 1][j] + Vv[i - 1][j - 1];
						}
					}
				}
				// 打印查看
				for (size_t i = 0; i < Vv.size(); ++i)
				{
					for (size_t j = 0; j < Vv[i].size(); ++j)
					{
						cout << Vv[i][j] << " ";
					}
					cout << endl;
				}

				return Vv;
			}
		};
		vector<vector<int>> ret = Solution().generate(5);
	}
}
